package 二叉树;
import java.util.*;
public class travelTree {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){}
        TreeNode(int val){
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public static TreeNode buildTree(String[] nodes){
        if(nodes == null || nodes.length == 0 || nodes[0].equals("null"))
            return null;
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int index = 1;
        // 队列为空说明没有下一层，节点列表结束说明已经没有节点，循环结束
        while(!queue.isEmpty() && index < nodes.length){
            TreeNode cur = queue.poll();
            // 每一轮循环index会增加2，所以内层if也需要进行index < nodes.length的判断
            // 不然会报数组越界的异常，测试用例：[1,2,3,4,5,null,8,null,null,6,7,9]
            if(index < nodes.length && !nodes[index].equals("null")){
                cur.left = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(cur.left);
            }
            index++;
            if(index < nodes.length && !nodes[index].equals("null")){
                cur.right = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(cur.right);
            }
            index++;
        }
        return root;
    }

    public static List<Integer> preOrder(TreeNode root){
        List<Integer> list = new ArrayList<>();
        preBfs(root, list);
        return list;
    }
    public static void preBfs(TreeNode root, List<Integer> list){
        if(root == null) return;
        // 入栈前添加节点
        list.add(root.val);
        // 左子树入栈
        preBfs(root.left, list);
        // 左子树出栈，有右子树，右子树入栈
        preBfs(root.right, list);
    }
    public static List<Integer> preStack(TreeNode root){
        List<Integer> list = new ArrayList<>();
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        while(!stack.isEmpty() || root != null){
            while(root != null){
                // 入栈前添加节点
                list.add(root.val);
                // 左子树入栈
                stack.push(root);
                root = root.left;
            }
            if(!stack.isEmpty()){
                // 左子树出栈，有右子树，右子树入栈
                root = stack.pop();
                root = root.right;
            }
        }
        return list;
    }
    public static List<Integer> inOrder(TreeNode root){
        List<Integer> list = new ArrayList<>();
        inBfs(root, list);
        return list;
    }
    public static void inBfs(TreeNode root, List<Integer> list){
        if(root == null) return;
        // 左子树入栈
        inBfs(root.left, list);
        // 出栈，记录左节点
        list.add(root.val);
        // 左节点有右子树，右子树入栈
        inBfs(root.right, list);
    }
    public static List<Integer> inStack(TreeNode root){
        List<Integer> list = new ArrayList<>();
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        while(!stack.isEmpty() || root != null){
            while(root != null){
                // 左子树入栈
                stack.push(root);
                root = root.left;
            }
            if(!stack.isEmpty()){
                // 出栈，记录左节点
                root = stack.pop();
                list.add(root.val);
                // 左节点有右子树，右子树入栈
                root = root.right;
            }
        }
        return list;
    }
    public static List<Integer> postOrder(TreeNode root){
        List<Integer> list = new ArrayList<>();
        postBfs(root, list);
        return list;
    }
    public static void postBfs(TreeNode root, List<Integer> list){
        if(root == null) return;
        // 左子树入栈
        postBfs(root.left, list);
        // 右子树入栈
        postBfs(root.right, list);
        // 记录节点
        list.add(root.val);
    }
    public static List<Integer> postStack(TreeNode root){
        List<Integer> list = new ArrayList<>();
        ArrayDeque<TreeNode> stack1 = new ArrayDeque<>();
        ArrayDeque<TreeNode> stack2 = new ArrayDeque<>();
        // 利用双栈实现后续非递归
        // 1 2 3：
        // 先序：1 2 3 根->左->右
        // 后续：2 3 1 左->右->根
        // 调换先序左右子树：1 3 2 根->右->左
        // 用另一个栈翻转：2 3 1 左->右->根 
        while(!stack1.isEmpty() || root != null){
            while(root != null){
                stack1.push(root);
                stack2.push(root);
                root = root.right;
            }
            if(!stack1.isEmpty()){
                root = stack1.pop();
                root = root.left;
            }
        }
        while(!stack2.isEmpty()){
            root = stack2.pop();
            list.add(root.val);
        }
        return list;
    }
    public static List<List<Integer>> levelOrder(TreeNode root){
        List<List<Integer>> res = new ArrayList<>();
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        // 层序：利用队列进行bfs
        // 队列为空说明没有下一层，循环结束
        while(!queue.isEmpty()){
            // 获取该层宽度
            int size = queue.size();
            // 用来记录该层节点值
            List<Integer> level = new ArrayList<>();
            // 遍历该层
            for(int i = 0; i < size; i++){
                // 获取该层节点
                TreeNode cur = queue.poll();
                // 添加节点值
                level.add(cur.val);
                // 节点有子节点，则将子节点加入下一层
                if(cur.left != null) queue.offer(cur.left);
                if(cur.right != null) queue.offer(cur.right);
            }
            // 将整层节点值列表进行记录
            res.add(level);
        }
        return res;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] nodes = sc.nextLine().split(" ");
        TreeNode root = buildTree(nodes);
        System.out.println("pre order: " + preOrder(root));
        System.out.println("non recur: " + preStack(root));
        System.out.println("in order: " + inOrder(root));
        System.out.println("non recur" + inStack(root));
        System.out.println("post order: " + postOrder(root));
        System.out.println("non recur: " + postStack(root));
        System.out.println("level order: " + levelOrder(root));
        sc.close();
    }
}
